#region Copyright Notice
// 
// 
//  
//  Copyright (c) 2009-2011 Anindya Chatterjee
//  
//  Licensed under the Apache License, Version 2.0 (the "License");
//  you may not use this file except in compliance with the License.
//  You may obtain a copy of the License at
//  
//      http://www.apache.org/licenses/LICENSE-2.0
//  
//  Unless required by applicable law or agreed to in writing, software
//  distributed under the License is distributed on an "AS IS" BASIS,
//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//  See the License for the specific language governing permissions and
//  limitations under the License.
// 
// 
#endregion
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using AbstractClass.Extensions.Serialization;
using AbstractClass.Linq;

namespace AbstractClass.Collections.Generic
{
    /// <summary>
    /// Represents a tree data structure in which each node has at most two child nodes, usually distinguished as "left" and "right".
    /// </summary>
    /// <typeparam name="T">The type of the data in the tree.</typeparam>
    [Serializable]
    public class BinaryTree<T> : AbstractTree<T, BinaryTreeNode<T>>, IBinaryTree<T>
    {
        private readonly List<BinaryTreeNode<T>> _availableNodes = new List<BinaryTreeNode<T>>();

        #region Overrides of AbstractTree<T,BinaryTreeNode<T>>

        /// <summary>
        /// Gets the leaf nodes of the tree.
        /// </summary>
        /// <value>The leaf nodes.</value>
        public override IEnumerable<BinaryTreeNode<T>> Leaves
        {
            get { return Root == null ? null : _availableNodes.Where(treeNode => treeNode.ChildCount == 0); }
        }

        /// <summary>
        /// Gets all nodes in the tree.
        /// </summary>
        /// <value>The nodes in the tree.</value>
        public override IEnumerable<BinaryTreeNode<T>> ToEnumerable
        {
            get
            {
                if (Root == null) return null;
                return Root.ToEnumerable(BinaryTreeTraversalOrder.InOrder);
            }
        }

        /// <summary>
        /// Adds the node to the tree.
        /// </summary>
        /// <param name="node">The node to add.</param>
        /// <returns>
        /// <c>true</c> if added successfully; otherwise, <c>false</c>.
        /// </returns>
        public override bool AddNode(BinaryTreeNode<T> node)
        {
            return AddNode(node, -1);
        }

        /// <summary>
        /// Adds the node to the tree.
        /// </summary>
        /// <param name="node">The node to add.</param>
        /// <param name="depth">The depth at which the node to be attached.</param>
        /// <returns>
        /// <c>true</c> if added successfully; otherwise, <c>false</c>.
        /// </returns>
        /// <exception cref="InvalidOperationException">Specified depth is greater than tree height.</exception>
        public override bool AddNode(BinaryTreeNode<T> node, int depth)
        {
            node.Tree = this;

            if (Root == null)
            {
                Root = node;
                node.Parent = null;
                OnNodeChange(node);
                return true;
            }

            // if depth is -1 it will attempt to enter the new node as the nearest available node's child
            if (depth == -1)
            {
                if (_availableNodes.Count > 0)
                {
                    _availableNodes.ElementAt(0).AddChild(node);
                    return true;
                }
            }

            if (depth == 0)
            {
                node.AddChild(Root);
                Root = node;
                node.Parent = null;
                return true;
            }

            try
            {
                _availableNodes.Where(tNode => tNode.Depth >= depth).FirstOrDefault().AddChild(node);
            }
            catch (NullReferenceException)
            {
                throw new NullReferenceException(LanguageResource.AddNodeNotPossible);
            }
            catch (InvalidOperationException)
            {
                throw new InvalidOperationException(LanguageResource.DepthCantBeGreaterThanTheTreeHeight);
            }
            return false;
        }

        /// <summary>
        /// Deletes the node from the tree.
        /// </summary>
        /// <param name="node">The node to delete.</param>
        /// <returns>
        /// <c>true</c> if deleted successfully; otherwise, <c>false</c>.
        /// </returns>
        public override bool DeleteNode(BinaryTreeNode<T> node)
        {
            bool result = Delete(node);
            if (_availableNodes.Contains(node))
            {
                _availableNodes.Remove(node);
            }
            return result;
        }

        private bool Delete(BinaryTreeNode<T> removeNode)
        {
            if (removeNode == null)
                return false;

            bool wasHead = removeNode.IsRoot();

            if (removeNode.IsLeaf)
            {
                if (removeNode.IsLeftChild)
                    ((BinaryTreeNode<T>) removeNode.Parent).Left = null;
                else
                    ((BinaryTreeNode<T>) removeNode.Parent).Right = null;

                removeNode.Parent = null;
            }
            else if (removeNode.ChildCount == 1)
            {
                if (removeNode.HasLeftChild)
                {
                    removeNode.Left.Parent = removeNode.Parent;
                    if (wasHead)
                        Root = removeNode.Left;

                    if (removeNode.IsLeftChild)
                        ((BinaryTreeNode<T>) removeNode.Parent).Left = removeNode.Left;
                    else
                        ((BinaryTreeNode<T>) removeNode.Parent).Right = removeNode.Left;
                }
                else
                {
                    removeNode.Right.Parent = removeNode.Parent;

                    if (wasHead)
                        Root = removeNode.Right;
                    if (removeNode.IsLeftChild)
                        ((BinaryTreeNode<T>) removeNode.Parent).Left = removeNode.Right;
                    else
                        ((BinaryTreeNode<T>) removeNode.Parent).Right = removeNode.Right;
                }

                removeNode.Parent = null;
                removeNode.Left = null;
                removeNode.Right = null;
            }
            else
            {
                BinaryTreeNode<T> successorNode = removeNode.Left;
                while (successorNode.Right != null)
                {
                    successorNode = successorNode.Right;
                }
                removeNode.Value = successorNode.Value;
                DeleteNode(successorNode);
            }
            return true;
        }

        /// <summary>
        /// Tries to get the node specified by <paramref name="data"/> from the tree.
        /// </summary>
        /// <param name="data">The data to search.</param>
        /// <returns>
        /// A <see cref="BinaryTreeNode&lt;T&gt;"/> associated with <paramref name="data"/>
        /// if fetching successful; otherwise, <c>null</c>.
        /// </returns>
        public override BinaryTreeNode<T> TryGetNode(T data)
        {
            return Root == null ? null : ToEnumerable.FirstOrDefault(x => x.Value.Equals(data));
        }

        /// <summary>
        /// Determines whether the specified <paramref name="node"/> is in the tree or not.
        /// </summary>
        /// <param name="node">The node to find.</param>
        /// <returns>
        /// 	<c>true</c> if the tree has the specified node; otherwise, <c>false</c>.
        /// </returns>
        public override bool HasNode(BinaryTreeNode<T> node)
        {
            return Root != null && ToEnumerable.Contains(node);
        }

        /// <summary>
        /// Traverses the whole tree in a order specified by <see cref="BinaryTreeTraversalOrder"/> and executes an <see cref="Action&lt;T&gt;"/> specified by
        /// <paramref name="treeVisitor"/> in each node once.
        /// </summary>
        /// <param name="treeVisitor">The tree visitor which will get executed at each node of the tree once.</param>
        /// <param name="traversalOrder">Order of the tree traversal.</param>
        public void Traverse(Action<BinaryTreeNode<T>> treeVisitor, BinaryTreeTraversalOrder traversalOrder)
        {
            if (Root == null) return;
            Root.ToEnumerable(traversalOrder).Process(treeVisitor);
        }

        /// <summary>
        /// Clears this instance and remove all the nodes attached to it.
        /// </summary>
        public override void Clear()
        {
            if (Root == null) return;
            Root.Delete();
            Root = null;
        }

        /// <summary>
        /// Gets the sub-tree rooted at <paramref name="node"/>.
        /// </summary>
        /// <param name="node">The root node of the sub-tree.</param>
        /// <returns>
        /// A <see cref="AbstractTree&lt;T, TNode&gt;" /> object with <paramref name="node"/> at its root.
        /// </returns>
        public override AbstractTree<T, BinaryTreeNode<T>> GetSubtree(BinaryTreeNode<T> node)
        {
            var subTree = new BinaryTree<T> {Root = node};
            subTree.RebuildAvailableNodes();
            return subTree;
        }

        /// <summary>
        /// Creates a clone of this instance.
        /// </summary>
        /// <returns>
        /// A new <see cref="AbstractTree&lt;T, TNode&gt;" /> object, which is a clone of this instance.
        /// </returns>
        public override AbstractTree<T, BinaryTreeNode<T>> Clone()
        {
            try
            {
                Stream stream = this.ToBinaryStream();
                BinaryTree<T> newTree = this.FromBinaryStream(stream);
                return newTree;
            }
            catch
            {
                return MemberwiseClone() as BinaryTree<T>;
            }
        }

        #endregion

        /// <summary>
        /// Gets a value indicating whether this instance is a full binary tree.
        /// </summary>
        /// <value>
        /// 	<c>true</c> if this instance is a full binary tree; otherwise, <c>false</c>.
        /// </value>
        public bool IsFullBinaryTree
        {
            get
            {
                if (Root == null) return false;
                IEnumerable<BinaryTreeNode<T>> nodes =
                    ToEnumerable.Where(node => !Leaves.Contains(node));
                return !nodes.Any(binaryTreeNode => binaryTreeNode.ChildCount < 2);
            }
        }

        /// <summary>
        /// Gets a value indicating whether this instance is a perfect binary tree.
        /// </summary>
        /// <value>
        /// 	<c>true</c> if this instance is a perfect binary tree; otherwise, <c>false</c>.
        /// </value>
        public bool IsPerfectBinaryTree
        {
            get
            {
                if (Root == null) return false;
                return IsFullBinaryTree && Leaves.All(node => node.Depth == Height);
            }
        }

        /// <summary>
        /// Gets a value indicating whether this instance is a balanced binary tree.
        /// </summary>
        /// <value>
        /// 	<c>true</c> if this instance is a balanced binary tree; otherwise, <c>false</c>.
        /// </value>
        public bool IsBalancedBinaryTree
        {
            get { return Root != null && Leaves.All(node => node.Depth == Height || node.Depth == Height - 1); }
        }

        /// <summary>
        /// Gets a value indicating whether this instance is a degenerated binary tree.
        /// </summary>
        /// <value>
        /// 	<c>true</c> if this instance is a degenerated binary tree; otherwise, <c>false</c>.
        /// </value>
        public bool IsDegeneratedBinaryTree
        {
            get
            {
                return Root != null &&
                       ToEnumerable.All(
                           node => node.ChildCount == 1 || node.ChildCount == 0);
            }
        }

        /// <summary>
        /// Gets or sets a collection of binary tree nodes at the specified <paramref name="depth"/>.
        /// </summary>
        /// <value></value>
        public IEnumerable<BinaryTreeNode<T>> this[int depth]
        {
            get { return Root.ToEnumerable(BinaryTreeTraversalOrder.DepthFirst).Where(x => x.Depth == depth); }
            set
            {
                foreach (var treeNode in value)
                {
                    AddNode(treeNode, depth);
                }
            }
        }

        #region IBinaryTree<T> Members

        /// <summary>
        /// Called when a node changes.
        /// </summary>
        /// <param name="node">The changed node.</param>
        public void OnNodeChange(BinaryTreeNode<T> node)
        {
            if (_availableNodes.Contains(node) && node.ChildCount == 2)
                _availableNodes.Remove(node);
            if (!_availableNodes.Contains(node) && node.ChildCount != 2)
                _availableNodes.Add(node);
        }

        #endregion

        /// <summary>
        /// Rebuilds the available nodes in the tree.
        /// </summary>
        public void RebuildAvailableNodes()
        {
            ToEnumerable.Process(OnNodeChange);
        }
    }
}